package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2019/12/27
 */
public class PathSum {

    public static void main(String[] args) {
        System.out.println(pathSum(create(), 3));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(-2);
        ret.right = new TreeNode(-3);
        ret.right.left = new TreeNode(-2);
        ret.left.left = new TreeNode(1);
        ret.left.right = new TreeNode(3);
        ret.left.left.left = new TreeNode(-1);
        return ret;
    }

    public static int pathSum(TreeNode root, int sum) {
        int ret = 0;
        if ( root != null ) {
            ret += sum(root, sum, 0);
            ret += pathSum(root.left, sum);
            ret += pathSum(root.right, sum);
        }
        return ret;
    }

    private static int sum(TreeNode node, int sum, int leave) {
        int ret = 0;
        if ( node != null ) {
            if ( leave + node.val == sum )
                ret++;
            ret += sum(node.left, sum, leave + node.val);
            ret += sum(node.right, sum, leave + node.val);
        }
        return ret;
    }

}
